#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <omp.h>

#define MAX_NODES 10000
#define INF INT_MAX

typedef struct {
    int dest;
    float weight;
} Edge;

typedef struct {
    Edge* edges;
    int count;
} AdjList;

AdjList graph[MAX_NODES];
float dist[MAX_NODES][MAX_NODES];
int num_nodes = 0;

void initialize_graph() {
    for (int i = 0; i < MAX_NODES; i++) {
        graph[i].edges = NULL;
        graph[i].count = 0;
        for (int j = 0; j < MAX_NODES; j++) {
            dist[i][j] = INF;
        }
        dist[i][i] = 0;
    }
}

void add_edge(int src, int dest, float weight) {
    // 无向图添加双向边
    graph[src].count++;
    graph[src].edges = realloc(graph[src].edges, graph[src].count * sizeof(Edge));
    graph[src].edges[graph[src].count-1].dest = dest;
    graph[src].edges[graph[src].count-1].weight = weight;
    
    graph[dest].count++;
    graph[dest].edges = realloc(graph[dest].edges, graph[dest].count * sizeof(Edge));
    graph[dest].edges[graph[dest].count-1].dest = src;
    graph[dest].edges[graph[dest].count-1].weight = weight;
    
    // 更新直接距离
    dist[src][dest] = weight;
    dist[dest][src] = weight;
    
    // 更新节点总数
    if (src >= num_nodes) num_nodes = src + 1;
    if (dest >= num_nodes) num_nodes = dest + 1;
}

void load_graph(const char* filename) {
    FILE* file = fopen(filename, "r");
    if (!file) {
        perror("Error opening file");
        exit(1);
    }

    char line[256];
    while (fgets(line, sizeof(line), file)) {
        int src, dest;
        float weight;
        if (sscanf(line, "%d,%d,%f", &src, &dest, &weight) == 3) {
            add_edge(src, dest, weight);
        }
    }
    fclose(file);
}

void dijkstra(int src) {
    int visited[MAX_NODES] = {0};
    
    // 初始化距离
    for (int i = 0; i < num_nodes; i++) {
        dist[src][i] = INF;
    }
    dist[src][src] = 0;
    
    for (int count = 0; count < num_nodes; count++) {
        // 找到未访问的最小距离节点
        int u = -1;
        float min_dist = INF;
        for (int v = 0; v < num_nodes; v++) {
            if (!visited[v] && dist[src][v] < min_dist) {
                min_dist = dist[src][v];
                u = v;
            }
        }
        
        if (u == -1) break;
        visited[u] = 1;
        
        // 更新邻接节点距离
        for (int i = 0; i < graph[u].count; i++) {
            int v = graph[u].edges[i].dest;
            float w = graph[u].edges[i].weight;
            if (!visited[v] && dist[src][u] + w < dist[src][v]) {
                dist[src][v] = dist[src][u] + w;
            }
        }
    }
}

void parallel_shortest_path(int num_threads) {
    #pragma omp parallel for num_threads(num_threads)
    for (int src = 0; src < num_nodes; src++) {
        dijkstra(src);
    }
}

int main(int argc, char** argv) {
    if (argc != 4) {
        printf("Usage: %s <flower_csv> <mouse_csv> <num_threads>\n", argv[0]);
        return 1;
    }

    initialize_graph();
    
    // 加载两个数据集
    load_graph(argv[1]); // flower数据集
    load_graph(argv[2]); // mouse数据集
    
    int num_threads = atoi(argv[3]);
    double start = omp_get_wtime();
    parallel_shortest_path(num_threads);
    double end = omp_get_wtime();
    
    printf("Total nodes: %d\n", num_nodes);
    printf("Computation time: %.4f seconds\n", end - start);
    
    // 示例输出（可修改为实际需求）
    printf("Sample distances:\n");
    printf("dist[0][100] = %.2f\n", dist[0][100]);
    printf("dist[500][1000] = %.2f\n", dist[500][1000]);
    
    // 释放内存
    for (int i = 0; i < num_nodes; i++) {
        free(graph[i].edges);
    }
    
    return 0;
}